package lc;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class Q990 {

    Runnable runnable = () -> {

    };

    public boolean equationsPossible(String[] equations) {
        // 将所有的
        // 通过parent归类
        int[] parent = new int[26];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        for (String equation : equations) {
            if (equation.charAt(1) == '=') {
                // 设置parent
                union(parent, equation.charAt(0), equation.charAt(3));
            }
        }
        for (String equation : equations) {
            if (equation.charAt(1) == '!') {
                if (find(parent, equation.charAt(0)) == find(parent, equation.charAt(3))) {
                    return false;
                }
            }
        }
        return true;
    }

    // 将c1和c2合并成一个群组中
    public void union(int[] parent, char c1, char c2) {
        parent[find(parent, c1)] = find(parent, c2);
    }

    // 寻找c所在的群组
    private int find(int[] parent, char c) {
        int index = c - 'a';
        while (parent[index] != index) {
            parent[index] = parent[parent[index]];
            index = parent[index];
        }
        return index;
    }

}
